#include "ActiveVar.h"

#include <algorithm>
#include <iomanip>

#define DEBUG true

void ActiveVar::Debug(Function* func_)
{
    
    for (auto bb: func_->get_basic_blocks())
    {
        std::cout<<"\033[31m"<<bb->get_name()<<"\n"<<"\033[0m";
        std::cout<<"\033[34m    Def:\033[0m";
        for (auto a : def[bb])
        {
            std::cout<<a->get_name()<<", ";
        }
        std::cout<<"\n";
        std::cout<<"\033[34m    not_phi_use: \033[0m";
        for (auto b : not_phi_use[bb])
        {
            std::cout<<b->get_name()<<", \033[0m";
        }
        std::cout<<"\n";
        std::cout<<"\033[34m    phi_use: \033[0m";
        for (auto c : phi_use[bb])
        {
            std::cout<<c->get_name()<<", \033[0m";
        }
        std::cout<<"\n";
        std::cout<<"\033[34m    live_in: \033[0m";
        for (auto d : live_in[bb])
        {
            std::cout<<d->get_name()<<", ";
        }
        std::cout<<"\n";
        std::cout<<"\033[34m    live_out: \033[0m";
        for (auto f : live_out[bb])
        {
            std::cout<<f->get_name()<<", ";
        }
        std::cout<<"\n";
    }
}
void ActiveVar::execute() {
    for (auto &func : this->module->get_functions()) 
    {
        if (func->get_basic_blocks().empty()) 
        {
            continue;
        } 
        else 
        {
            func_ = func;
            for (auto bb: func_->get_basic_blocks())
            {
                bb->set_live_in({});
                bb->set_live_out({});
                GetUD(bb);
            }
            Getlive(func_);
            for (auto bb : func_->get_basic_blocks())
            {
                bb->set_live_in(live_in[bb]);
                bb->set_live_out(live_out[bb]);
            }
            if (DEBUG)
            {
                Debug(func_);
            }   
        }
    }
}

void ActiveVar::GetUD(BasicBlock* bb)
{
    def.insert({bb,{}});
    not_phi_use.insert({bb,{}});
    phi_use.insert({bb,{}});
    for (auto instruction : bb->get_instructions())
    {
        if (instruction->is_phi())
        {
            for (auto op : instruction->get_operands())
            {
                if (!dynamic_cast<BasicBlock*>(op) && (def[bb].find(op) == def[bb].end()))
                    phi_use[bb].insert(op);
            }
        }
        else
        {
            for (auto op : instruction->get_operands())     //先分析use，再分析def，a = a + 1
            {
                if ( !(dynamic_cast<Constant*>(op) || (dynamic_cast<Function*>(op)) || dynamic_cast<BasicBlock*>(op)))    //不是常数，基本块，或者函数
                    if (def[bb].find(op) == def[bb].end())      //在def中无定值
                        not_phi_use[bb].insert(op);
            }
        }

        if (!instruction->is_void())                        //void 以外的所有语句都为def
            def[bb].insert(instruction);
    }
}
void ActiveVar::Getlive(Function* func_)
{
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (auto bb : func_->get_basic_blocks())               //得到bb的IN和OUT
        {   
            std::set<Value*> tmp_live_out = {};
            for (auto succ_bb : bb->get_succ_basic_blocks())    //对bb的每一个后继块，计算IN[succ_bb]，
            {
                auto tmp_use = not_phi_use[succ_bb];            //succ_bb的无phi指令use集合
                if (phi_use[succ_bb].size() > 0)               //存在phi指令
                {
                    for (auto phi_op:phi_use[succ_bb])
                    {
                        for (auto Use : phi_op->get_use_list())     //遍历该变量的使用链，将所有[op,bb]的op置为活跃
                        {
                            auto op_num = Use.arg_no_;

                            auto instruction = dynamic_cast<Instruction *>(Use.val_);
                            
                            if (instruction->is_phi() && (instruction->get_operand(op_num+1) == bb))    //这个变量有效
                            {
                                tmp_use.insert(phi_op);
                            }
                        }
                    }
                }

                //将这个succ_bb的IN并到bb的OUT里
                std::set<Value *> outsubdef = {};
                std::set<Value *> tmp_in = {};
                std::set_difference(live_out[succ_bb].begin(), live_out[succ_bb].end(), def[succ_bb].begin(), def[succ_bb].end(), std::inserter(outsubdef, outsubdef.begin()));
                std::set_union(tmp_use.begin(), tmp_use.end(), outsubdef.begin(), outsubdef.end(), std::inserter(tmp_in, tmp_in.begin()));
                std::set<Value *> tmp;
                std::set_union(tmp_live_out.begin(), tmp_live_out.end(), tmp_in.begin(), tmp_in.end(), std::inserter(tmp, tmp.begin()));
                tmp_live_out = tmp;                     
            }

            //bb的后继块遍历完后,更新bb的IN和OUT,并判断是否有改变
            live_out[bb] = tmp_live_out;            //OUT
            auto tmp_live_in = tmp_live_out;
            std::set<Value *> tmp1,tmp2,tmp3;
            std::set_difference(live_out[bb].begin(), live_out[bb].end(), def[bb].begin(), def[bb].end(), std::inserter(tmp1, tmp1.begin()));
            //把phi指令涉及的所有“右边”变量均放在bb的IN中
            std::set_union(tmp1.begin(), tmp1.end(), not_phi_use[bb].begin(), not_phi_use[bb].end(), std::inserter(tmp2, tmp2.begin()));
            std::set_union(tmp2.begin(), tmp2.end(), phi_use[bb].begin(), phi_use[bb].end(), std::inserter(tmp3, tmp3.begin()));
            //  tmp3即为IN[bb]

            if (tmp3.size() > live_in[bb].size()){
                live_in[bb] = tmp3;
                flag = true;
            }
        }
    }
    return ; 
}